K-th missing positive number

Time: O(LogN); Space: O(1); easy

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5

Output: 9

Explanation:

  • The missing positive integers are [1,5,6,8,9,10,12,13,…]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2

Output: 6

Explanation:

  • The missing positive integers are [5,6,7,…]. The 2nd missing positive integer is 6.

Constraints:

  • 1 <= len(arr) <= 1000

  • 1 <= arr[i] <= 1000

  • 1 <= k <= 1000

  • arr[i] < arr[j] for 1 <= i < j <= len(arr)

Hints:

  1. Keep track of how many positive numbers are missing as you scan the array.

1. Binary Search [O(LogN),O(1)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def findKthPositive(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        def check(arr, k, x):
            return arr[x]-(x+1) < k

        left, right = 0, len(arr)-1

        while left <= right:
            mid = left + (right-left)//2
            if not check(arr, k, mid):
                right = mid - 1
            else:
                left = mid + 1

        return right + 1 + k  # arr[right] + (k-(arr[right]-(right+1))) if right >= 0 else k

[2]:

s = Solution1()

arr = [2,3,4,7,11]
k = 5
assert s.findKthPositive(arr, k) == 9

arr = [1,2,3,4]
k = 2
assert s.findKthPositive(arr, k) == 6